package com.lyh.test.utils;

import java.util.ArrayList;
import java.util.List;

public class TreePlusTable <K extends Comparable<K>, V>{
    //元素个数
    private int size;

    //树高度
    private int high;

    //度
    private int degree;

    //最少度数
    private int degreeFloor;

    //根节点
    private Node root;

    public TreePlusTable(int degree){
        this.degree = degree;
        this.degreeFloor = degree / 2;
        this.root = new Node(true, true);
        this.high = 1;
    }

    public void put(K k, V v){
        this.root.put(k, v);
    }

    public void delete(K k){
        this.root.delete(k);
    }

    public class Node<K extends Comparable<K>, V>{

        //是否根节点
        private boolean isRoot;

        //是否叶子节点
        private boolean isLeaf;

        //前一个节点
        private Node prev;

        //下一个节点
        private Node next;

        //父节点
        private Node parent;

        //key
        private List<K> keys;

        //数据
        private List<V> datas;

        //孩子指针
        private List<Node> children;


        public Node(boolean isRoot, boolean isLeaf){
            this.isRoot = isRoot;
            this.isLeaf = isLeaf;
            this.keys = new ArrayList<>(degree);
            if(isLeaf){
                this.datas = new ArrayList<>(degree);
            }
        }

        public Node(boolean isRoot, List<K> keys, List<V> datas){
            this.isRoot = isRoot;
            this.isLeaf = !isRoot;
            this.keys = new ArrayList<>(keys);
            this.datas = new ArrayList<>(datas);
        }

        public Node(boolean isRoot, boolean isLeaf, List<K> keys, List<Node> children){
            this.isRoot = isRoot;
            this.isLeaf = isLeaf;
            this.keys = new ArrayList<>(keys);
            this.children = new ArrayList<>(children);
        }

        /**
         * 二分查找
         * @param keys
         * @param key
         * @return
         */
        public int binarySearch(List<K> keys, K key){
            if(keys == null || keys.size() == 0){
                return -1;
            }
            int startIndex = 0;
            int endIndex = keys.size() - 1;
            while (startIndex <= endIndex){
                int mid = (startIndex + endIndex) / 2;
                int i = key.compareTo(keys.get(mid));
                if(i > 0){
                    startIndex  = mid + 1;
                }else if(i < 0){
                    endIndex = mid - 1;
                }else{
                    return mid;
                }
            }
            return -1;
        }

        /**
         * 搜索节点
         * @param node
         * @return
         */
        public Node nodeSearch(Node node, K key){
            //当前节点没有了孩子节点，当前节点就是叶子节点
            if(node.children == null || node.children.size() <= 0){
                return node;
            }
            //搜索当前keys确定孩子节点的指向；(当前key 在keys中 应该是 >= keys中的)
            int startIndex = 0;
            int endIndex = node.keys.size() - 1;
            int childrenIndex = node.keys.size();
            while (startIndex <= endIndex){
                int mid = (startIndex + endIndex) / 2;
                int i = key.compareTo((K)node.keys.get(mid));
                if(i > 0){
                    startIndex  = mid + 1;
                } else if(i < 0){
                    endIndex = mid - 1;
                    childrenIndex = mid;
                } else {
                    childrenIndex = mid + 1;
                    startIndex  = mid + 1;
                    endIndex = mid - 1;
                }
            }
            //找到了当前节点的孩子节点
            Node childNode = (Node)node.children.get(childrenIndex);
            //递归搜索节点
            return nodeSearch(childNode, key);
        }

        public void put(K k, V v){
            size = size + 1;
            System.out.println("当前第" + size + "个元素");
            Node node = nodeSearch(this, k);
            //节点赋值
            int index = binarySearch(node.keys, k);
            if (index == -1) {
                node.keys.add(k);
                node.datas.add(v);
            }else{
                node.keys.add(index + 1, k);
                node.datas.add(index + 1, v);
            }
            //判断节点是否需要分裂
            if(node.keys.size() >= degree){
                int mid = node.keys.size() / 2;
                Node rigth = new Node(false, node.keys.subList(mid, node.keys.size()), node.datas.subList(mid, node.datas.size()));
                Node next = node.next;
                node.keys = new ArrayList(node.keys.subList(0, mid));
                node.datas = new ArrayList(node.datas.subList(0, mid));
                //开始分裂之后，当前节点不会是根节点了
                node.isRoot = false;
                if(next != null){
                    rigth.prev = node;
                    rigth.next = next;
                    node.next = rigth;
                    next.prev = rigth;
                }else{
                    node.next = rigth;
                    rigth.prev = node;
                }
                handleParent(node);
            }
        }

        /**
         * 处理父节点
         * @param node
         */
        public void handleParent(Node node){
            Node parent = node.parent;
            if(parent != null){
                //为父节点的keys添加右节点的第一个key
                parent.keys.add(node.next.keys.get(0));
                //为父节点的children添加右节点指向
                parent.children.add(node.next);

                //如果是root节点需要右节点的第一个key移除
                if(!node.isLeaf){
                    node.next.keys.remove(0);
                }

                if(parent.keys.size() >= degree){
                    int mid = parent.keys.size() / 2;
                    Node rigth = new Node(false, false, parent.keys.subList(mid, parent.keys.size()), parent.children.subList(mid + 1, parent.children.size()));
                    Node next = parent.next;
                    parent.keys = new ArrayList(parent.keys.subList(0, mid));
                    parent.children = new ArrayList(parent.children.subList(0, mid + 1));
                    if(next != null){
                        rigth.prev = parent;
                        rigth.next = next;
                        parent.next = rigth;
                        next.prev = rigth;
                    }else{
                        parent.next = rigth;
                        rigth.prev = parent;
                    }
                    //父节点分裂之后需要将children的父指针指向新的父节点
                    rigth.children.forEach(child -> {
                        Node tempChild = (Node)child;
                        tempChild.parent = rigth;
                    });
                    //递归处理父节点
                    handleParent(parent);
                    //为右节点指向父节点
                    rigth.parent = parent.parent;
                }else{
                    node.next.parent = parent;
                }

            }else {
                Node newRoot = new Node(true, false);
                high++;
                newRoot.keys.add(node.next.keys.get(0));
                //如果是root节点需要右节点的第一个key移除
                if(!node.isLeaf){
                    node.next.keys.remove(0);
                }
                newRoot.children = new ArrayList(degree + 1);
                newRoot.children.add(node);
                newRoot.children.add(node.next);
                node.parent = newRoot;
                node.next.parent = newRoot;
                root = newRoot;
            }
        }

        //删除元素
        public void delete(K key){
            //搜索出要删除元素的节点
            Node node = nodeSearch(this, key);
            int index = binarySearch(node.keys, key);
            if(index == -1){
                return;
            }
            //执行删除元素
            node.keys.remove(index);
            node.datas.remove(index);
            size--;
            //根元素删除之后直接返回
            if(node.isRoot){
                return;
            }
            //检测元素删除之后元素个数是否小于最小度数
            if(node.keys.size() < degreeFloor){
                //向左右兄弟节点借
                if(node.prev != null && node.parent.equals(node.prev.parent) &&  node.prev.keys.size() > degreeFloor){
                    //当前节点左兄弟节点满足借
                    node.keys.add(0, node.prev.keys.remove(node.prev.keys.size() - 1));
                    node.datas.add(0, node.prev.keys.remove(node.prev.datas.size() - 1));
                    int childrenIndex = node.parent.children.indexOf(node);
                    node.parent.keys.remove(childrenIndex);
                    node.parent.keys.add(childrenIndex, node.keys.get(0));
                }else if(node.next != null && node.parent.equals(node.next.parent) && node.next.keys.size() > degreeFloor){
                    //当前节点右兄弟节点满足借
                    node.keys.add(node.keys.size() - 1, node.next.keys.remove(0));
                    node.datas.add(node.keys.size() - 1, node.next.keys.remove(0));
                    int childrenIndex = node.parent.children.indexOf(node);
                    node.parent.keys.remove(childrenIndex);
                    node.parent.keys.add(childrenIndex, node.keys.get(0));

                //左右兄弟节点都穷，则进行元素合并
                }else if(node.prev != null  && node.parent.equals(node.prev.parent) && node.prev.keys.size() < degree ){
                    //当前节点左兄弟节点满足合并
                    node.prev.keys.addAll(node.keys);
                    node.prev.datas.addAll(node.datas);
                    //处理父节点keys和children
                    int nodeIndex = node.parent.children.indexOf(node);
                    node.parent.keys.remove(nodeIndex - 1);
                    node.parent.children.remove(nodeIndex);
                    node.prev.next = node.next;
                    if(node.next != null){
                        node.next.prev = node.prev;
                    }

                    //处理父节点合并
                    handleMergeParent(node.parent);
                    node.parent = null;
                }else if(node.next != null  && node.parent.equals(node.next.parent) && node.next.keys.size() < degree){
                    Node next = node.next;
                    node.keys.addAll(next.keys);
                    node.datas.addAll(next.datas);
                    int nodeIndex = node.parent.children.indexOf(next);
                    node.parent.keys.remove(nodeIndex - 1);
                    node.parent.children.remove(nodeIndex);
                    node.next = next.next;
                    if(node.next != null){
                        node.next.prev = node;
                    }
                    //处理父节点合并
                    handleMergeParent(node.parent);
                    next.parent = null;
                    node = null;
                }
            }
        }

        public void handleMergeParent(Node node){
            if(node.isRoot){
                if(node.keys.size() < 1) {
                    Node newRoot = (Node) node.children.get(0);
                    newRoot.isRoot = true;
                    root = newRoot;
                    node.children.clear();
                    node.keys.clear();
                    node.parent = null;
                    high--;
                }
            }else{
                if(node.keys.size() < degreeFloor){
                    if(node.prev != null  && node.parent.equals(node.prev.parent) && node.prev.keys.size() < degree ){
                        //当前节点左兄弟节点满足合并
                        Node child = (Node) node.children.get(0);
                        node.keys.add(0, child.keys.get(0));
                        node.prev.keys.addAll(node.keys);
                        node.prev.children.addAll(node.children);
                        node.prev.next = node.next;
                        if(node.next != null){
                            node.next.prev = node.prev;
                        }
                        int nodeIndex = node.parent.children.indexOf(node);
                        node.parent.keys.remove(nodeIndex - 1);
                        node.parent.children.remove(nodeIndex);

                    }else if(node.next != null  && node.parent.equals(node.prev.parent) && node.prev.keys.size() < degree ){
                        Node child = (Node) node.next.children.get(0);
                        node.next.keys.add(0, child.keys.get(0));
                        node.keys.add(node.next.keys);
                        node.children.add(node.next.children);
                        node.next = node.next.next;
                        if(node.next != null){
                            node.next.prev = node;
                        }
                        int nodeIndex = node.parent.children.indexOf(node.next);
                        node.parent.keys.remove(nodeIndex - 1);
                        node.parent.children.remove(nodeIndex);
                    }
                    handleMergeParent(node.parent);
                    node.parent = null;
                }
            }

        }
    }

    public static void main(String[] args) {
        List<Integer> keys = new ArrayList<Integer>(){{add(1);add(2);add(3);add(4);add(5);add(6);add(7);add(8);add(9);add(10);add(11);add(12);add(13);add(14);}};
        List<String> datas = new ArrayList<String>(){{add("1");add("2");add("3");add("4");add("5");add("6");add("7");add("8");add("9");add("10");add("11");add("l2");add("13");add("14");}};
        TreePlusTable<Integer, String> treePlusTable = new TreePlusTable<>(5);
        for (int i = 0; i < 14; i++) {
            Integer key = keys.get(i);
            String data = datas.get(i);
            treePlusTable.put(key, data);
        }

        System.out.println(treePlusTable);

        treePlusTable.delete(7);
        System.out.println(treePlusTable);

    }
}
